package week02

// 207. 课程表
// https://leetcode-cn.com/problems/course-schedule/

func canFinish(numCourses int, prerequisites [][]int) bool {
    var inDeg = make(map[int]int)   // 统计入度
    var graph = make(map[int][]int)
    for _, edges := range prerequisites {
        graph[edges[1]] = append(graph[edges[1]], edges[0])
        inDeg[edges[0]]++
    }
    return bfs(graph, numCourses, inDeg)
}

func bfs(graph map[int][]int, numCourses int, inDeg map[int]int) bool {
    var learned = 0
    var queue []int
    // 找出所有可学习的课程
    for n := 0; n < numCourses; n++ {
        if inDeg[n] == 0 {
            queue = append(queue, n)
        }
    }

    for len(queue) > 0 {
        val := queue[0]
        queue = queue[1:]   // 已学习，出队
        learned++

        for _, edge := range graph[val] {
            inDeg[edge]--
            if inDeg[edge] == 0 {
                queue = append(queue, edge) // 可学习，入队
            }
        }
    }
    return learned == numCourses
}
